package algorithm;

import java.util.Stack;

public class leetcode_top100_02 {
    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public static void main(String[] args) {
        ListNode l1=new ListNode(2);
        l1.next=new ListNode(4);
        l1.next.next=new ListNode(9);

        ListNode l2=new ListNode(5);
        l2.next=new ListNode(6);
        l2.next.next=new ListNode(4);
        l2.next.next.next=new ListNode(9);

        addTwoNumbers(l1,l2);

    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        Stack<Integer> stack1=new Stack();
        Stack<Integer> stack2=new Stack();
        ListNode result=new ListNode();
        ListNode p=result;
        while(l1!=null){
            stack1.add(l1.val);
            l1=l1.next;
        }
        while(l2!=null){
            stack2.add(l2.val);
            l2=l2.next;
        }

        int a=stack1.pop();
        int b=stack2.pop();
        int shang=(a+b)/10;
        int yu=(a+b)%10;
        p.val=yu;
        while(stack1.size()>0 && stack2.size()>0){
            a=stack1.pop();
            b=stack2.pop();
            yu=(a+b+shang)%10;
            shang=(a+b+shang)/10;
            p.next=new ListNode(yu);
            p=p.next;
        }
        while(stack1.size()>0){
            a=stack1.pop();
            b=0;
            yu=(a+b+shang)%10;
            shang=(a+b+shang)/10;
            p.next=new ListNode(yu);
            p=p.next;
        }
        while(stack2.size()>0){
            a=0;
            b=stack2.pop();
            yu=(a+b+shang)%10;
            shang=(a+b+shang)/10;
            p.next=new ListNode(yu);
            p=p.next;
        }
        if(shang==1){ //处理最后一位进位
            p.next=new ListNode(shang);
        }
        return result;
    }
}
